package com.hqq.leetcode.dp;

/**
 * CoinLineI 硬币排成线I
 * Description:
 * There are n coins in a line. Two players take turns to take one or two coins from right side until there are no more coins left.
 * The player who take the last coin wins.
 * Could you please decide the first play will win or lose?
 * Input:
 * 1
 * 2
 * 3
 * 4
 * 5
 * Output:
 * true
 * true
 * false
 * true
 * true
 * <p>
 * Created by heqianqian on 2017/9/18.
 */
public class CoinLineI {

    public static void main(String[] args) {
        int[] array = new int[]{1, 2, 3, 4, 5};
        CoinLineI cl = new CoinLineI();
        for (int i = 0; i < array.length; i++) {
            System.out.println(cl.firstWillWin(array[i]));
        }
    }

    /*
     * @param n: An integer
     * @return: A boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int n) {
        // write your code here
        return helper2(n);
    }

    /*使用dp思想解决*/
    public boolean helper1(int n) {
        if (n <= 0) {
            return false;
        }
        if (n <= 2) {
            return true;
        }
        boolean[] dp = new boolean[n + 1];
        dp[3] = true;
        for (int i = 4; i <= n; i++) {
            dp[i] = dp[i - 4];
        }
        return !dp[n];
    }

    /*直接只用规律解决*/
    public boolean helper2(int n) {
        return n % 3 != 0;
    }
}
